import queue
import random
c_ij = [
    [0,5,21,13,6,15,12,20],
    [5,0,16,18,7,12,19,17],
    [21,16,0,33,16,7,17,11],
    [13,18,33,0,17,26,16,29],
    [6,7,16,17,0,9,12,14],
    [15,12,7,26,9,0,10,5],
    [18,19,17,16,12,10,0,13],
    [20,17,11,29,14,5,13,0]
]
N = len(c_ij)
inf = 100000

def Kruskal(c_ij):
    #edges存储[权值，端点，端点]，按权值从小到大排序
    edges = []
    for i in range(N):
        for j in range(N):
            if j != i:
                edges.append((c_ij[i][j],i,j))
    edges.sort()

    mst = []#mst记录生成树的结点
    reps = [i for i in range(N)]#reps存储每个结点当前所属元组的标识，初始时每个结点标识都不同
    for w,v1,v2 in edges:
        
        if reps[v1] != reps[v2]:
            mst.append((v1,v2,w))
            if len(mst) == N - 1:
                break

            #讲v1,v2的标识统一
            reps1,reps2 = reps[v1],reps[v2]
            for i in range(N):
                if reps[i] == reps1:
                    reps[i] = reps2
    return mst

def Prim(c_ij):
    mst = [None] * N
    cands = queue.PriorityQueue()
    cands.put((0,0,0))
    count = 0
    while count < N and cands:
        w,v1,v2 = cands.get()
        if mst[v2]:
            continue
        mst[v2] = (v1,v2,w)
        count += 1
        for v in range(N):
            if not mst[v]:
                cands.put((c_ij[v2][v],v2,v)) 
    return mst


def eul(mst):
    ##将最小生成树的边加倍
    mst1 = [(item[0],item[1]) for item in mst] + [(item[1],item[0]) for item in mst]
    print(mst1)
    pioneer = random.choice(mst1)
    # print(pioneer)
    stack1 = [inf,3,0]
    mst1.remove((stack1[-2],stack1[-1]))
    route = [3,0]
    while len(stack1)>1:
       # print("stack1:",stack1)
        next_to = []
        for v1,v2 in mst1:
            if v1 == stack1[-1] and v2 != v1 and v2 != stack1[-2]:
                next_to.append((v1,v2))
        if next_to:
            next = random.choice(next_to)        
            stack1.append(next[1])
            mst1.remove(next)
            route.append(next[1])
                       
        if not next_to:        
            stack1.pop()
            route.append(stack1[-1])
    route.pop()
    return route
def get_tsp(route_eul,c_ij):
    route = []
    for item in route_eul:
        if item not in route:
            route.append(item)
    leng = 0
    for i in range(len(route)):
        leng += c_ij[route[i-1]][route[i]]
    return route,leng



mst = Prim(c_ij)
print(mst)
route_eul = eul(mst)
print(route_eul)
print(get_tsp(route_eul,c_ij))

